<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <title>回溯算法求最大工作效益 | Gm&#39;s Blog</title>
  <meta name="keywords" content=" algorithm ">
  <meta name="description" content="回溯算法求最大工作效益 | Gm&#39;s Blog">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="description" content="个人简介">
<meta property="og:type" content="website">
<meta property="og:title" content="关于">
<meta property="og:url" content="http:&#x2F;&#x2F;linignan.cn&#x2F;about&#x2F;index.html">
<meta property="og:site_name" content="Gm&#39;s Blog">
<meta property="og:description" content="个人简介">
<meta property="og:locale" content="zh-CN">
<meta property="og:updated_time" content="2019-11-20T03:25:34.000Z">
<meta name="twitter:card" content="summary">


<link rel="icon" href="/img/avatar.jpg">

<link href="/css/style.css?v=1.0.1" rel="stylesheet">

<link href="/css/hl_theme/sublime.css?v=1.0.1" rel="stylesheet">

<link href="//cdn.bootcss.com/animate.css/3.5.2/animate.min.css" rel="stylesheet">
<link href="//cdn.bootcss.com/font-awesome/4.7.0/css/font-awesome.min.css" rel="stylesheet">

<script src="//code.jquery.com/jquery-3.3.1.min.js"></script>
<script src="/js/jquery.autocomplete.min.js?v=1.0.1" ></script>

<script src="//cdn.bootcss.com/highlight.js/9.12.0/highlight.min.js"></script>
<script>
    hljs.initHighlightingOnLoad();
</script>

<script src="//cdn.bootcss.com/nprogress/0.2.0/nprogress.min.js"></script>



<script src="//cdn.bootcss.com/jquery-cookie/1.4.1/jquery.cookie.min.js" ></script>

<script src="/js/iconfont.js?v=1.0.1" ></script>

<link rel="alternate" href="/atom.xml" title="Gm's Blog" type="application/atom+xml">
</head>
<div style="display: none">
  <input class="theme_disqus_on" value="false">
  <input class="theme_preload_comment" value="false">
  <input class="theme_blog_path" value="">
</div>

<body>
<aside class="nav">
    <div class="nav-left">
        <a href="/" class="avatar_target">
    <img class="avatar" src="/img/avatar.jpg" />
</a>
<div class="author">
    <span>Gm&#39;s Blog</span>
</div>

<div class="icon">
    
        
        <a title="rss" href="/atom.xml" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-rss"></use>
                </svg>
            
        </a>
        
    
        
        <a title="github" href="https://github.com/G1950" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-github"></use>
                </svg>
            
        </a>
        
    
        
        <a title="facebook" href="https://facebook.com/guangming.pan.3" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-facebook"></use>
                </svg>
            
        </a>
        
    
        
        <a title="weibo" href="https://weibo.com/u/7075432820" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-weibo"></use>
                </svg>
            
        </a>
        
    
        
        <a title="zhihu" href="https://www.zhihu.com/people/guang-ming-7-19/activities" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-zhihu"></use>
                </svg>
            
        </a>
        
    
        
        <a title="csdn" href="https://me.csdn.net/weixin_42098924" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-csdn"></use>
                </svg>
            
        </a>
        
    
        
        <a title="email" href="mailto:1950661299@qq.com" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-email"></use>
                </svg>
            
        </a>
        
    
        
        <a title="qq" href="http://wpa.qq.com/msgrd?v=3&uin=1950661299&site=qq&menu=yes" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-qq"></use>
                </svg>
            
        </a>
        
    
</div>




<ul>
    <li><div class="all active">全部文章<small>(4)</small></div></li>
    
        
            
            <li><div data-rel="算法设计与分析">算法设计与分析<small>(3)</small></div>
                
            </li>
            
        
    
</ul>
<div class="left-bottom">
    <div class="menus">
    
    
    
    
    </div>
    <div><a class="about  hasFriend  site_url"  href="/about">关于</a><a style="width: 50%"  class="friends">友链</a></div>
</div>
<input type="hidden" id="yelog_site_posts_number" value="4">
<input type="hidden" id="yelog_site_word_count" value="2k">
<div style="display: none">
    <span id="busuanzi_value_site_uv"></span>
    <span id="busuanzi_value_site_pv"></span>
</div>

    </div>
    <div class="nav-right">
        <div class="friends-area">
    <div class="friends-title">
        友情链接
        <i class="back-title-list"></i>
    </div>
    <div class="friends-content">
        <ul>
            
            <li><a target="_blank" href="http://yelog.org/">叶落阁</a></li>
            
        </ul>
    </div>
</div>
        <div class="title-list">
    <form onkeydown="if(event.keyCode==13){return false;}">
        <input class="search" type="text" placeholder="以 in: 开头进行全文搜索" autocomplete="off"id="local-search-input" >
        <i class="cross"></i>
        <span>
            <label for="tagswitch">Tags:</label>
            <input id="tagswitch" type="checkbox" style="display: none" />
            <i id="tagsWitchIcon"></i>
        </span>
    </form>
    <div class="tags-list">
    
    <li class="article-tag-list-item">
        <a class="color5">algorithm</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">哈夫曼编码</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">数据结构</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">随机数</a>
    </li>
    
    <div class="clearfix"></div>
</div>

    
    <div id="local-search-result">

    </div>
    
    <nav id="title-list-nav">
        
        <a id="top" class=""
           href="/2019/11/20/About/"
           data-tag=""
           data-author="光明" >
            <span class="post-title" title="关于本博客">关于本博客</span>
            <span class="post-date" title="2019-11-20 11:36:00">2019/11/20</span>
        </a>
        
        <a  class="算法设计与分析 "
           href="/2019/11/20/samp/"
           data-tag="随机数"
           data-author="光明" >
            <span class="post-title" title="随机数选择">随机数选择</span>
            <span class="post-date" title="2019-11-20 13:44:11">2019/11/20</span>
        </a>
        
        <a  class="算法设计与分析 "
           href="/2019/11/19/Backtracking-algo-benefit/"
           data-tag="algorithm"
           data-author="光明" >
            <span class="post-title" title="回溯算法求最大工作效益">回溯算法求最大工作效益</span>
            <span class="post-date" title="2019-11-19 00:30:00">2019/11/19</span>
        </a>
        
        <a  class="算法设计与分析 "
           href="/2019/11/17/Huffman/"
           data-tag="哈夫曼编码,数据结构"
           data-author="光明" >
            <span class="post-title" title="哈夫曼编码问题">哈夫曼编码问题</span>
            <span class="post-date" title="2019-11-17 18:00:00">2019/11/17</span>
        </a>
        
    </nav>
</div>
    </div>
    <div class="hide-list">
        <div class="semicircle">
            <div class="brackets first"><</div>
            <div class="brackets">&gt;</div>
        </div>
    </div>
</aside>
<div class="post">
    <div class="pjax">
        <article id="post-Backtracking-algo-benefit" class="article article-type-post" itemscope itemprop="blogPost">
    
        <h1 class="article-title">回溯算法求最大工作效益</h1>
    
    <div class="article-meta">
        
        
        <span class="author"><a>光明</a></span>
        
        
        <span class="book">
            
                <a  data-rel="算法设计与分析">算法设计与分析</a>
            
        </span>
        
        
        <span class="tag">
            
            <a class="color5">algorithm</a>
            
        </span>
        
    </div>
    <div class="article-meta">
        
        创建时间:<time class="date" title='更新时间: 2019-11-21 01:18:57'>2019-11-19 00:30</time>
        
    </div>
    <div class="article-meta">
        
        <span>字数:363</span>
        
        
        <span id="busuanzi_container_page_pv">
            阅读:<span id="busuanzi_value_page_pv">
                <span class="count-comment">
                    <span class="spinner">
                      <div class="cube1"></div>
                      <div class="cube2"></div>
                    </span>
                </span>
            </span>
        </span>
        
        
    </div>
    
    <div class="toc-ref">
    
        <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#null"><span class="toc-text">求最大工作效益</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#null"><span class="toc-text">1、问题介绍</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#null"><span class="toc-text">2、详细代码</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#null"><span class="toc-text">3、相关文件</span></a></li></ol></li></ol>
    
<style>
    .left-col .switch-btn,
    .left-col .switch-area {
        display: none;
    }
    .toc-level-3 i,
    .toc-level-3 ol {
        display: none !important;
    }
</style>
</div>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h1><span id="求最大工作效益">求最大工作效益</span></h1><h2><span id="1-问题介绍">1、问题介绍</span></h2><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;设有A，B，C，D，5人从事J1，J2，J3，J4，J5，五项工作，每人只能从事一项，他们的效益如图所示，求最佳安排使得效益最高。</p>
<p><img src="https://img-blog.csdnimg.cn/20191119001915133.png#pic_center?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5ODkyNA==,size_16,color_FFFFFF,t_70" alt="问题图片"></p>
<h2><span id="2-详细代码">2、详细代码</span></h2><pre><code class="c">#include &lt;stdio.h&gt;

#define N 5

int arrys[N][N] = {
        {10, 11, 10, 4,  7},
        {13, 10, 10, 8,  5},
        {5,  9,  7,  7,  4},
        {15, 12, 10, 11, 5},
        {10, 11, 8,  8,  4}
};

int job[N];    //分配工作数组
int savejob[N];
int used[N];    //存0或1，0表示工作未分配，1为已经分配
int sum;    //存储最大工作效益

//工作分配函数
void search(int i, int total) {
    int j;
    if (i == N) //判断是否最后一个人分配工作
    {
        if (sum &lt; total) {
            sum = total;
            for (j = 0; j &lt; N; ++j) {
                savejob[j] = job[j];
            }
        }
        return;
    }
    for (j = 0; j &lt; N; ++j) {
        if (!used[j])    //判断工作是否分配
        {
            job[i] = j + 1; //j+1 -&gt; 1-5为分配的工作下标
            used[j] = 1;  //分配状态设为1，表示已分配
            search(i + 1, total + arrys[i][j]);    //下一个人的工作分配，
            used[j] = 0;    //回溯工作置为未分配状态
        }

    }

}

//主函数
int main(int argc, char *argv[]) {
    int i;
    for (i = 0; i &lt; N; ++i) {    //初始化工作分配状态数组
        used[i] = 0;
    }
    sum = 0;
    search(0, 0);
    for (i = 0; i &lt;N ; ++i) {
        printf(&quot;%c分配到的工作为：J%d\n&quot;,i+65,savejob[i]);
    }
    printf(&quot;最大工作效益为：%d\n&quot;, sum);
}</code></pre>
<h2><span id="3-相关文件">3、相关文件</span></h2><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href="https://github.com/G1950/algorithm/tree/master/benefit" target="_blank" rel="noopener">Github</a></p>

      
      
	<hr><span style="font-style: italic;color: gray;"> 转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1950661299@qq.com </span>
    </div>
</article>


<p>
    <a  class="dashang" onclick="dashangToggle()">赏</a>
</p>


<div class="article_copyright">
    <p><span class="copy-title">文章标题:</span>回溯算法求最大工作效益</p>
    <p><span class="copy-title">文章字数:</span><span class="post-count">363</span></p>
    <p><span class="copy-title">本文作者:</span><a  title="Gm&#39;s Blog">Gm&#39;s Blog</a></p>
    <p><span class="copy-title">发布时间:</span>2019-11-19, 00:30:00</p>
    <p><span class="copy-title">最后更新:</span>2019-11-21, 01:18:57</p>
    <span class="copy-title">原始链接:</span><a class="post-url" href="/2019/11/19/Backtracking-algo-benefit/" title="回溯算法求最大工作效益">http://linignan.cn/2019/11/19/Backtracking-algo-benefit/</a>
    <p>
        <span class="copy-title">版权声明:</span><i class="fa fa-creative-commons"></i> <a rel="license noopener" href="http://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank" title="CC BY-NC-SA 4.0 International" target = "_blank">"署名-非商用-相同方式共享 4.0"</a> 转载请保留原文链接及作者。
    </p>
</div>





    




    </div>
    <div class="copyright">
        <p class="footer-entry">©2016-2019 yelog</p>
<p class="footer-entry">Built with <a href="https://hexo.io/" target="_blank">Hexo</a> and <a href="https://github.com/yelog/hexo-theme-3-hexo" target="_blank">3-hexo</a> theme</p>

    </div>
    <div class="full-toc">
        <button class="full"><span class="min "></span></button>
<button class="post-toc-menu"><span class="post-toc-menu-icons"></span></button>
<div class="post-toc"><span class="post-toc-title">目录</span>
    <div class="post-toc-content">

    </div>
</div>
<a class="" id="rocket" ></a>

    </div>
</div>
<div class="acParent"></div>

<div class="hide_box" onclick="dashangToggle()"></div>
<div class="shang_box">
    <a class="shang_close"  onclick="dashangToggle()">×</a>
    <div class="shang_tit">
        <p>喜欢就点赞,疼爱就打赏</p>
    </div>
    <div class="shang_payimg">
        <div class="pay_img">
            <img src="/img/alipay.jpg" class="alipay" title="扫码支持">
            <img src="/img/weixin.jpg" class="weixin" title="扫码支持">
        </div>
    </div>
    <div class="shang_payselect">
        <span><label><input type="radio" name="pay" checked value="alipay">支付宝</label></span><span><label><input type="radio" name="pay" value="weixin">微信</label></span>
    </div>
</div>


</body>
<script src="/js/jquery.pjax.js?v=1.0.1" ></script>

<script src="/js/script.js?v=1.0.1" ></script>
<script>
    var img_resize = 'default';
    /*作者、标签的自动补全*/
    $(function () {
        $('.search').AutoComplete({
            'data': ['@光明','@冯辉','#algorithm','#哈夫曼编码','#数据结构','#随机数',],
            'itemHeight': 20,
            'width': 418
        }).AutoComplete('show');
    })
    function initArticle() {
        /*渲染对应的表格样式*/
        
            $(".post .pjax table").addClass("green_title");
        

        /*渲染打赏样式*/
        
        $("input[name=pay]").on("click", function () {
            if($("input[name=pay]:checked").val()=="weixin"){
                $(".shang_box .shang_payimg .pay_img").addClass("weixin_img");
            } else {
                $(".shang_box .shang_payimg .pay_img").removeClass("weixin_img");
            }
        })
        

        /*高亮代码块行号*/
        
        $('pre code').each(function(){
            var lines = $(this).text().split('\n').length, widther='';
            if (lines>99) {
                widther = 'widther'
            }
            var $numbering = $('<ul/>').addClass('pre-numbering ' + widther).attr("unselectable","on");
            $(this).addClass('has-numbering ' + widther)
                    .parent()
                    .append($numbering);
            for(var i=1;i<=lines;i++){
                $numbering.append($('<li/>').text(i));
            }
        });
        

        /*访问数量*/
        
        $.getScript("//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js");
        

        /*代码高亮，行号对齐*/
        $('.pre-numbering').css('line-height',$('.has-numbering').css('line-height'));

        
        
    }

    /*打赏页面隐藏与展示*/
    
    function dashangToggle() {
        $(".shang_box").fadeToggle();
        $(".hide_box").fadeToggle();
    }
    

</script>

<!--加入行号的高亮代码块样式-->

<style>
    pre{
        position: relative;
        margin-bottom: 24px;
        border-radius: 10px;
        border: 1px solid #e2dede;
        background: #23241f;
        overflow: hidden;
    }
    code.has-numbering{
        margin-left: 30px;
    }
    code.has-numbering.widther{
        margin-left: 35px;
    }
    .pre-numbering{
        margin: 0px;
        position: absolute;
        top: 0;
        left: 0;
        width: 20px;
        padding: 0.35em 0px 0.7em 0px;
        border-right: 1px solid #C3CCD0;
        text-align: center;
        color: #AAA;
        background-color: ;
    }
    .pre-numbering.widther {
        width: 35px;
    }
</style>

<!--自定义样式设置-->
<style>
    
    
    .nav {
        width: 622px;
    }
    .nav.fullscreen {
        margin-left: -622px;
    }
    .nav-left {
        width: 200px;
    }
    
    
    @media screen and (max-width: 1468px) {
        .nav {
            width: 492px;
        }
        .nav.fullscreen {
            margin-left: -492px;
        }
        .nav-left {
            width: 100px;
        }
    }
    
    
    @media screen and (max-width: 1024px) {
        .nav {
            width: 492px;
            margin-left: -492px
        }
        .nav.fullscreen {
            margin-left: 0;
        }
        .nav .hide-list.fullscreen {
            left: 492px
        }
    }
    
    @media screen and (max-width: 426px) {
        .nav {
            width: 100%;
        }
        .nav-left {
            width: 100%;
        }
    }
    
    
    .nav-right .title-list nav a .post-title, .nav-right .title-list #local-search-result a .post-title {
        color: #383636;
    }
    
    
    .nav-right .title-list nav a .post-date, .nav-right .title-list #local-search-result a .post-date {
        color: #5e5e5f;
    }
    
    
    .nav-right nav a.hover, #local-search-result a.hover{
        background-color: #e2e0e0;
    }
    
    

    /*列表样式*/
    
    .post .pjax article .article-entry>ol, .post .pjax article .article-entry>ul, .post .pjax article>ol, .post .pjax article>ul{
        border: #e2dede solid 1px;
        border-radius: 10px;
        padding: 10px 32px 10px 56px;
    }
    .post .pjax article .article-entry li>ol, .post .pjax article .article-entry li>ul,.post .pjax article li>ol, .post .pjax article li>ul{
        padding-top: 5px;
        padding-bottom: 5px;
    }
    .post .pjax article .article-entry>ol>li, .post .pjax article .article-entry>ul>li,.post .pjax article>ol>li, .post .pjax article>ul>li{
        margin-bottom: auto;
        margin-left: auto;
    }
    .post .pjax article .article-entry li>ol>li, .post .pjax article .article-entry li>ul>li,.post .pjax article li>ol>li, .post .pjax article li>ul>li{
        margin-bottom: auto;
        margin-left: auto;
    }
    

    /* 背景图样式 */
    
    


    /*引用块样式*/
    

    /*文章列表背景图*/
    
    .nav-right:before {
        content: ' ';
        display: block;
        position: absolute;
        left: 0;
        top: 0;
        width: 100%;
        height: 100%;
        opacity: 0.3;
        background: url("https://i.loli.net/2019/07/22/5d3521411f3f169375.png");
        background-repeat: no-repeat;
        background-position: 50% 0;
        -ms-background-size: cover;
        -o-background-size: cover;
        -moz-background-size: cover;
        -webkit-background-size: cover;
        background-size: cover;
    }
    

    
</style>







</html>
